class Disjoinset{
public:
    vector<int> parent,rank;

    Disjoinset(int n):parent(n), rank(n,1){
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }

    int find(int x){
        if(parent[x] != x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void merge(int x,int y){
        int rootx = find(x);
        int rooty = find(y);
        if(rootx != rooty){
            if(rank[rootx]<rank[rooty]){
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            rank[rootx] += rank[rooty];
        }
    }
};
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if(grid.empty()) return 0;

        int x = grid.size();
        int y = grid[0].size();

        Disjoinset ds(x*y);

        for(int i=0;i<x;i++){
            for(int j=0;j<y;j++){
                if(grid[i][j] == 1){
                    int index=i*y+j;
                    if(j>0 && grid[i][j-1]==1){
                        int lef = i*y+j-1;
                        ds.merge(index,lef);
                    }
                    if(i>0 && grid[i-1][j]==1){
                        int top = (i-1)*y + j;
                        ds.merge(index,top);
                    }
                }
            }
        }
        int res = 0;
        for(int i=0;i<x;i++){
            for(int j=0;j<y;j++){
                if(grid[i][j] == 1){
                    int d = ds.find(i*y+j);
                    res = max(res,ds.rank[d]);
                }
            }
        }
        return res;
    }
};
